1. Field of Invention
This invention relates to the identification and retrieval of digital data by a computing device.
2. Prior Art
A method for the discovery of digital data, such as images, that are organized for point-wise two dimensional presentation (2DDDs), that are similar to a target 2DDD is invented here. Formulae from algebraic topology [Spanier] are used to compute signatures that characterize equivalence classes of 2DDDs. The method leverages these “equivalence signatures” to find 2DDDs that are similar to target 2DDDs and, separately and alternatively, find 2DDDs that are dissimilar from the target 2DDDs. The most important examples of 2DDD are images, video frames and rasterized graphics data. In this invention, we will refer to such 2DDD simply as images.
The definition of “similarity”, and thus the features and method used to compute it, is idiosyncratic to the retrieval application [O'Connor]. In the case of image retrieval [Gonzalez], methods using entropy, moments, etc. as signatures, have been invented [5,933,823; 5,442,716]. Work in computer graphics has advanced these analytical methods by using an elementary result from topology, the Euler number of polyhedra, as a descriptor of boundary polygons of graphics objects [Foley]. Recently, a method for computing the Euler numbers of binary images using a chip design has been invented [7,027,649]. Another invention [7,246,314], uses closeness to a Gaussian model as a similarity measure for identifying similar videos.
The cost of implementing these methods is typically proportional to the product of the number of 2DDDs in the database with the cost of computing the distance between the target 2DDD and another 2DDD. The latter often [Raghavan] involves the computation of the projection angle between two vectors that represent the features (e.g., histogram of the text elements) of the 2DDDs. For large databases, this process can be both resource and time expensive. A two step method is required wherein, during the retrieval phase, the number of candidates for similarity is significantly reduced in a computationally inexpensive first step and then the traditional features can be applied to the reduced set of candidates.
Intuitively, if two 2DDDs are similar, then they should be deformable into each other without having to remove or glue together portions of 2DDDs. For example, if two images are rescalings and/or rotations of each other, then the images are similar. The field of topology provides a foundation for solving this problem. In particular, we appeal to homotopy invariants that characterize equivalence classes of maps between topological spaces [Bott].
We interpret each 2DDD as a sampling of maps from a two-dimensional presentation space to a n-dimensional topological space and seek homotopy equivalence classes of such maps. Mapping of the Cartesian subspace onto the two-dimensional sphere can be done by a number of methods. Here, we will ascribe the azimuthal and zenith angles (θ1,θ2) of the sphere, S2, as the horizontal and vertical coordinates, (x1, x2), on the image, or vice versa:
            θ      i        ≡                  2        ⁢                                  ⁢                  πx          i                            L        t              ,where the Li (i=1,2) are the lengths of the respective dimensions. In another embodiment, an embedding into three dimensional Euclidean space is first performed.
We work with 2DDDs that have at least two data planes, {tilde over (σ)}A(θ1,θ2), with maximum and minimum values, {tilde over (σ)}maxA and {tilde over (σ)}minA, respectively. The maximum and minimum values of each of the two planes are used to normalize their data to new minimum and maximum values, σmaxA and σminA respectively, through the expressions:
                                          σ            A                    ⁡                      (                                          θ                1                            ,                              θ                2                                      )                          =                                            [                                                                    σ                    max                    A                                    -                                      σ                    min                    A                                                                                                              σ                      ~                                        max                    A                                    -                                                            σ                      ~                                        min                    A                                                              ]                        ⁡                          [                                                                                          σ                      ~                                        A                                    ⁡                                      (                                                                  θ                        1                                            ,                                              θ                        2                                                              )                                                  -                                                      σ                    ~                                    max                  A                                            ]                                +                      σ            max            A                                              Eqn        .                                  ⁢        1            
Additional normalizations of the 2DDD, such as scaling to a fixed width and height and the like, may also be performed.
To leverage the equivalence classes of the Second Homotopy Group [Bott], π2(S2)=Z, we select pairs of the normalized planes of the 2DDD and interpret them as the maps from the world sphere onto the target sphere:σ:S2→S2 (θ1,θ2)→(σ1(θ1,θ2),σ2(θ1,θ2))  Eqn. 2
An example of such a choice is the two planes of chroma pixel data in a YCC color space representation of images. If objects have been segmented from the 2DDD then the data for these objects are themselves 2DDDs. We refer to each segmented portion of each pair of normalized planes henceforth as a “2DDD section” with its own map, σ. With the definition that two 2DDDs are similar if one can be continuously deformed into the other, the well-established results on equivalence classes of homotopic maps lead to the conclusions: If two 2DDD sections do not have the same value of π2(S2), then they are not similar. If none of the 2DDD sections from parent 2DDDs are similar to each other, then those parent 2DDDs are not similar to each other.
The equivalence signature, ξ[σ], of a 2DDD section is given by the value of π2(S2) for the section computed as [Schwarz]
                                          ξ            ⁡                          [              σ              ]                                ≡                                    π              2                        ⁡                          [              σ              ]                                      =                              -                          1                              4                ⁢                                                                  ⁢                π                                              ⁢                      ∫                                                  ⁢                                          ⅆ                2                            ⁢                                                θsinσ                  2                                ⁡                                  [                                                                                                              ∂                                                      σ                            1                                                                                                    ∂                                                      θ                            1                                                                                              ⁢                                                                        ∂                                                      σ                            2                                                                                                    ∂                                                      θ                            2                                                                                                                -                                                                                            ∂                                                      σ                            1                                                                                                    ∂                                                      θ                            2                                                                                              ⁢                                                                        ∂                                                      σ                            2                                                                                                    ∂                                                      θ                            1                                                                                                                                ]                                                                                        Eqn        .                                  ⁢        3            
Consider two 2DDD sections, σ and σ′ such that, at each point, the difference between the values of the maps is infinitesimal:σ′A(θ1,θ2)−σA(θ1,θ2)=εA(θ1,θ2)
An example of such a difference is the constant resealing and shifts of the data values at each pointσ′A(θ1,θ2)−σA(θ1,θ2)=αAσA(θ1,θ2)+βA  Eqn. 5for some fixed, small, real constants αA and βA. The difference in the values of the equivalence signatures for the two 2DDD sections, in term of the first one, σ, isΔξ[σ;ε]≡ξ[σ+ε]−ξ[σ]  Eqn. 6
Given a choice for the functions εA, a limit on the difference of the values of the equivalence signatures for two 2DDD sections can be set so that the 2DDD sections are still regarded as similar. For example, suppose we are interested in finding images whose color planes differ by no more than p percent at each pixel, then that values αA=p and βA=0 are used in the computation of Δξ[σ;ε]. Retrieval of similarity candidates then proceeds by finding those images with values of ξ[σ], denoted as ξ[σsimilar], for which the following inequalities hold:|ξ[σtarget]−ξ[σsimilar]|≦|Δξ[σtarget;ε]|  Eqn. 7
As an example for the reduction factor for the number of CPU cycles and other resources required to find similar sections of 2DDDs in a corpus, assume for simplicity that and that the equivalences signatures of the 2DDDs in the corpus are uniformly distributed in [ξmax,ξmin]. If for a target 2DDD section, the choice of εA leads to a value for Δξ[σ;ε], the reduction in the number of secondary features to be compared is
                              f          r                =                              (                                          2                ⁢                                                                        Δ                    ⁢                                                                                  ⁢                                          ξ                      ⁡                                              [                                                  σ                          ;                          ɛ                                                ]                                                                                                                          +              1                        )                                (                                          ξ                max                            -                              ξ                min                            +              1                        )                                              Eqn        .                                  ⁢        8            
In state of the art information retrieval methodologies, the feature vector which is used for each 2DDD would have to be compared to all NA feature vectors computed for the 2DDDs in the corpus. Upon employing the method invented here as a precursor to the feature vector comparison, the number of feature vectors to be compared would be reduced to frNc.